#include <iostream>
#include <cstdbool>
using namespace std;

namespace YX
{
    // 结点
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev;
        ListNode<T>* _next;
        T _data;
        
        ListNode(const T& data)
            :_prev(nullptr)
            ,_next(nullptr)
            ,_data(data)
        {
            _prev=this;
            _next=this;
        }
    };

    template<class T,class REF,class PTR>
    struct _list_iterator
    {
        ListNode<T>* _iterator;

        _list_iterator(ListNode<T>* it)
            :_iterator(it)
        {
    
        }
        
        bool operator==(const _list_iterator<T,REF,PTR>& list_it)
        {
            return this->_iterator==list_it._iterator;
        }

        bool operator!=(const _list_iterator<T,REF,PTR>& list_it)
        {
            return this->_iterator!=list_it._iterator;
        }

        REF operator*()
        {
            return _iterator->_data;
        }

        _list_iterator<T,REF,PTR>& operator++()
        {
            _iterator=_iterator->_next;

            return *this;
        }

        _list_iterator<T,REF,PTR> operator++(int)
        {
            _list_iterator<T,REF,PTR> tmp(_iterator);

            _iterator=_iterator->_next;

            return tmp;
        }
        PTR operator->()
        {
            return &(operator*());
        }

    };


    template<class T>
    class List 
    {
        private:
            typedef ListNode<T> Node;

            Node* _head;

        public:
                
            typedef _list_iterator<T,T&,T*> Iterator;
            typedef _list_iterator<T,const T&,const T*> const_Iterator;

            List()
                :_head(nullptr)
            {
                _head=new Node(T());
            }
            
            template<class InputIterator>
            List(InputIterator frist,InputIterator last)
                :_head(new Node(T()))
            {
                while(frist!=last)
                {
                    push_back(*frist);
                    frist++;
                }
            }

            List(const List<T>& l)
                :_head(new Node(T()))
            {
                List<T> tmp(l.begin(),l.end());

                swap(tmp);
            }

            List<T>& operator=(List<T> l)
            {
                swap(l);
            }

            void clear()
            {
                Iterator del=begin();
                while(del!=end())
                {
                    del=erase(del);
                }
            }

            ~List()
            {
                clear();
                delete _head;
                _head=nullptr;
            }

            void swap(List<T>& l)
            {
                std::swap(_head,l._head);
            }

            void push_back(const T& val)
            {
                Node* tail=_head->_prev;

                Node* newNode=new Node(val);

                tail->_next=newNode;
                newNode->_prev=tail;

                _head->_prev=newNode;
                newNode->_next=_head;
            }
           

            void pop_back()
            {
                Node* del=_head->_prev;

                Node* prev=del->_prev;

                delete del;

                _head->_prev=prev;
                prev->_next=_head;

            }

            void push_front(const T& val)
            {
                Node* next=_head->_next;

                Node* newNode=new Node(val);

                _head->_next=newNode;
                newNode->_prev=_head;

                newNode->_next=next;
                next->_prev=newNode;
            }

            void pop_front()
            {

                Node* del=_head->_next;

                Node* prev=del->_prev;

                prev->_prev=_head;
                _head->_next=prev;

                delete del;
            }

            Iterator begin()
            {
                return Iterator(_head->_next);
            }

            Iterator end()
            {
                return Iterator(_head);
            }
            
            const_Iterator begin() const 
            {
                return const_Iterator(_head->_next);
            }

            const_Iterator end() const 
            {
                return const_Iterator(_head);
            }

            Iterator insert(Iterator pos,const T& val)
            {
                Node* newNode=new Node(val);

                Node* curr=pos._iterator;

                curr->_prev->_next=newNode;
                newNode->_prev=curr->_prev;

                curr->_prev=newNode;
                newNode->_next=curr;
                

                return Iterator(newNode);
            }

            Iterator erase(Iterator pos)
            {
                Node* del=pos._iterator;

                Node* prev=del->_prev;
                Node* next=del->_next;

                prev->_next=next;
                next->_prev=prev;

                delete del;

                return Iterator(next);
            }
            
        
            Iterator find(const T& val)
            {
                Node* curr=_head->_next;

                while(curr!=_head)
                {
                    if(curr->_data==val)
                    {
                        return Iterator(curr);
                    }
                    curr=curr->_next;
                }
                return Iterator(_head);
            }

    };

    void TestList1()
    {
        List<int> l;

        l.push_back(1);
        l.push_front(0);

        List<int> copy=l;

        l.pop_back();
        l.pop_front();

        for(auto e:copy)
        {
            cout<<e<<endl;
        }
        
        auto pos=copy.find(1);
        cout<<*pos<<endl;

        pos=copy.find(2);
        cout<<*pos<<endl;
        

       // List<int> l;

       // l.push_back(1);
       // l.push_back(2);
       // l.push_back(3);
       // l.push_back(4);
       // l.push_back(5);
       // l.push_back(6);
       // l.push_back(7);

       // List<int> copy=l;

//        List<int> l;
//
//        l.push_back(1);
//        l.push_back(2);
//        l.push_back(3);
//        l.push_back(4);
//        l.push_back(5);
//        l.push_back(6);
//        l.push_back(7);
//
//        List<int>::Iterator it=l.begin();
//
//        while(it!=l.end())
//        {
//            cout<<*it<<" ";
//            ++it;
//        }
//        cout<<endl;
//        
//        l.insert(l.begin(),0);
//        
//        it=l.begin();
//
//        while(it!=l.end())
//        {
//            cout<<*it<<" ";
//            ++it;
//        }
//        cout<<endl;
//

    }

};
